Many man-made objects and structures of interest in aerial/overhead images, such as for example roofs of buildings and vehicles, can be modeled with polygons. The ability to quickly and effectively match models for broad classes of polygons to such images is of great importance in semi-automatic content-based image search/database retrieval, image analysis, and image understanding applications that are throughput-intensive.
Template matching methods are sometimes used to match specific polygons. However, these methods typically cannot efficiently accommodate variations in polygon size. Polygons are thus more traditionally detected by extracting primitive features such as edges, lines or corners, and assembling collections of these features into polygons. Various methods of this type are known to handle variations in polygon size and even variations in relative side lengths, such as described, for example in “Localizing Overlapping Parts by Searching the Interpretation Tree,” by W. Grimson and T. Lozano-Perez (IEEE Trans. Pattern Anal. Mach. Intell., vol. 9, no. 4, July 1987, pp. 469-482) and “Building Detection and Description from a Single Intensity Image,” by C. Lin and R. Nevatia (Comput. Vis. Image Understanding, 72, 2, Nov. 1998, pp. 101-121.) However, such methods often miss polygons altogether even when only a few features are missing from the image. Even when partial matches to polygons can be found, they tend to be ranked much lower than complete matches of lesser quality.
What is needed therefore, is a robust method of detecting polygons in overhead imagery that is based on the modeling of polygons in a manner that accommodates whole classes of polygons (e.g. all L-shaped polygons at any position, orientation, and size, even if corner detection fails to detect or accurately localize all the required polygon corners.